package Leetcode.排序;

import java.util.Arrays;

/**
 * @ClassName 归并排序
 * @since: 2023/7/31 11:20
 * @auth: kirito
 * @description:
 *
 **/
public class 归并排序 {
    public static void mergeSort(int[] nums, int left, int right) {
        // 终止条件
        if (left >= right) {
            return;
        }
        // 递归划分
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        // 合并子数组
        // 暂存需合并区间元素
        int[] tmp = new int[right - left + 1];
//        for (int k = left; k <= right; k++) {
//            tmp[k - left] = nums[k];
//        }
//        // 两指针分别指向左/右子数组的首个元素
//        int flag_l = 0, flag_r = mid - left + 1;
//
//        // 遍历合并左/右子数组
//        for (int i = left; i <= right; i++) {
//            // 从左子数组的起始索引开始，直到右子数组的终止索引
//            if (flag_l == mid - left + 1) { // 如果左子数组的所有元素都已合并，即左指针已经到达右子数组的起始索引
//                nums[i] = tmp[flag_r++]; // 从右子数组中取出下一个元素，并将其合并到原数组中
//            } else if (flag_r == right - left + 1 // 如果右子数组的所有元素都已合并，或者
//                    ||tmp[flag_l] <= tmp[flag_r]  ) { //
//                nums[i] = tmp[flag_l++]; // 从左子数组中取出下一个元素，并将其合并到原数组中
//            } else { // 如果右子数组的元素小于左子数组的元素
//                nums[i] = tmp[flag_r++]; // 从右子数组中取出下一个元素，并将其合并到原数组中
//            }
//        }
        int flag_l = left, flag_r = mid + 1, i = 0;
        while (flag_l <= mid && flag_r <= right) {
            if (nums[flag_l] <= nums[flag_r]) {
                tmp[i++] = nums[flag_l++];
            } else {
                tmp[i++] = nums[flag_r++];
            }
        }
        while (flag_l <= mid) {
            tmp[i++] = nums[flag_l++];
        }
        while (flag_r <= right) {
            tmp[i++] = nums[flag_r++];
        }
        for (flag_l = left, i = 0; flag_l <= right; flag_l++, i++) {
            nums[flag_l] = tmp[i];
        }
    }
    /*
    #include <stdio.h>
#include <stdlib.h>

void mergeSort(int arr[], int left, int right);

int main() {
    int arr[] = {4, 1, 7, 3, 5, 9, 2};
    printf("Hello, World\n");
    int len = sizeof(arr) / sizeof(arr[0]);
    mergeSort(arr, 0, len - 1); // 注意：len - 1 是数组的上界
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

void mergeSort(int arr[], int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);

    int temp[right - left + 1]; // 创建一个临时数组，其大小为right - left + 1
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    for (i = left, k = 0; i <= right; i++, k++) {
        arr[i] = temp[k];
    }
}

     */
    public static void main(String[] args) {
        int[] arr = {4, 1, 7, 3, 5, 9, 2};
        mergeSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

}
